package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description 523. 连续的子数组和
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.6.2
 */

public class T523 {
    public static void main(String[] args) {
        T523 t523 = new T523();
//        int[] nums = {23, 2, 4, 6, 7};
//        int k = 6;
        int[] nums = {23,2,4,6,6};
        int k = 7;
        boolean b = t523.checkSubarraySum(nums, k);
        System.out.println(b);
    }

    //纯暴力  时间复杂度 n*n
    public boolean checkSubarraySum1(int[] nums, int k) {
        for (int i = 0; i < nums.length - 1; i++) {
            int tmp = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                tmp += nums[j];
                if (tmp % k == 0) {
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 前缀和加hash表   sum[i]表示0-i之间的数据
     * sum[i]-sum[j+1] 表示i-j之间的子集合的和
     * (sum[i]-sum[j+1])%k ==0 表示子集合可以被k整除
     * sum[i]%k = sum[j+1]%k
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean checkSubarraySum(int[] nums, int k) {

        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        //当余数等于0时，可以直接返回true
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int t = sum % k;
            if (map.containsKey(t)) {
                Integer integer = map.get(t);
                if (i - integer > 1) {
                    return true;
                }
            } else {
                map.put(t, i);
            }
        }
        return false;
    }
}
